package java_thinking.unit_17;

/**
 * @Desc:
 *     1.LinkedList 特点:
 *          1.1 双向链表实现 底层数据结构 Node<E>
 *              private static class Node<E> {
 *                  E item;
 *                  Node<E> next;
 *                  Node<E> prev;
 *              }
 *          1.2 元素时有序的，输出顺序与输入顺序一致
 *          1.3 允许元素为 null
 *          1.4 所有指定位置的操作都是从头开始遍历进行的
 *          1.5 和 ArrayList 一样，不是同步容器
 *
 *     2.并发访问注意事项：
 *          linkedList 和 ArrayList 一样，不是同步容器。所以需要外部做同步操作，或者直接用 Collections.synchronizedList
 *          方法包一下；LinkedList 的迭代器都是 fail-fast 的: 如果在并发环境下，其他线程使用迭代器以外的方法修改数据，
 *          会导致 ConcurrentModificationException
 *     3.ArrayList VS LinkedList:
 *          ArrayList
 *              基于数组，在数组中搜索和读取数据是很快的。因此 ArrayList 获取数据的时间复杂度是O(1),因为继承了RandomAccess;
 *              但是添加、删除时该元素后面的所有元素都要移动，所以添加/删除数据效率不高；
 *              另外其实还是有容量的，每次达到阈值需要扩容，这个操作比较影响效率。
 *          LinkedList
 *              基于双端链表，添加/删除元素只会影响周围的两个节点，开销很低；
 *              只能顺序遍历，无法按照索引获得元素，因此查询效率不高；
 *              没有固定容量，不需要扩容；
 *              需要更多的内存，LinkedList 每个节点中需要多存储前后节点的信息，占用空间更多些
 *
 * @author: cww
 * @DateTime: 2019/4/29 17:30
 */

public class LinkedListTheory {
}
